package com.it.od.manual;

import java.util.Arrays;

/**
 * @author: liminghui
 * @date: 2024/3/29 20:55
 * @version: 1.0
 * @description: 手撕快排代码
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] nums = {6, 7, 4, 8, 5};
        quickSort(nums, 0, nums.length - 1);
        System.out.println(Arrays.toString(nums));
    }

    private static void quickSort(int[] nums, int left, int right) {
        if (left >= right) { // 递归结束条件
            return;
        }
        // 选基中
        int base = nums[left];
        int i = left; // 从左往右找第一个大于base的数
        int j = right; // 从右往左找第一个小于base的数
        while (i < j) {
            while (i < j && nums[j] >= base) {
                j--;
            }
            while (i < j && nums[i] <= base) {
                i++;
            }
            // i/j相遇交换i,j
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
        // 交换基准与相遇时的i/j
        nums[left] = nums[i];
        nums[i] = base;
        // 继续递归
        quickSort(nums, left, i - 1);
        quickSort(nums, i + 1, right);
    }

}
